# -*- coding: utf-8 -*-

"""剑指 Offer II 017. 含有所有字符的最短字符串
给定两个字符串 s 和 t 。返回 s 中包含 t 的所有字符的最短子字符串。如果 s 中不存在符合条件的子字符串，则返回空字符串 "" 。
如果 s 中存在多个符合条件的子字符串，返回任意一个。

注意： 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。

示例 1：
输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC" 
解释：最短子字符串 "BANC" 包含了字符串 t 的所有字符 'A'、'B'、'C'

示例 2：
输入：s = "a", t = "a"
输出："a"

示例 3：
输入：s = "a", t = "aa"
输出：""
解释：t 中两个字符 'a' 均应包含在 s 的子串中，因此没有符合条件的子字符串，返回空字符串。

提示：
1 <= s.length, t.length <= 105
s 和 t 由英文字母组成"""


class Solution:
    """典型的双指针+查表"""
    def minWindow(self, s: str, t: str) -> str:
        table = {}
        for n in range(65, 91):
            table[chr(n)] = 0
        for n in range(97, 123):
            table[chr(n)] = 0        
        for a in t:
            table[a] += 1
        
        head, tail = 0, 0
        shortest, substring = len(s), ''
        
        table[s[tail]] -= 1
        ln = 1
        while True:
            try:
                if tail < head:
                    tail = head

                if max(table.values()) == 0:
                    if ln <= shortest:
                        shortest = ln
                        substring = s[head: tail+1]
                    
                    table[s[head]] += 1
                    head += 1
                    ln -= 1
                else:
                    tail += 1
                    table[s[tail]] -= 1
                    ln += 1
            except IndexError:
                break
        
        return substring


if __name__ == '__main__':
    so = Solution()
    print(so.minWindow(s = "ADOBECODEBANC", t = "ABC"))
    print(so.minWindow(s = "a", t = "a"))
    print(so.minWindow(s = "a", t = "aa"))

